package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author zhangjy
 * @description 翻转二叉树
 * @date 2025/2/25 20:04
 */
public class InvertTree_226 {

    public static void main(String[] args) {
        InvertTree_226 invertTree226 = new InvertTree_226();
        System.out.println(invertTree226.invertTree(null));
    }

    /**
     * 为什么遍历顺序采用前序、后序都可以，但是中序就不行？
     * <p>
     * ——可以做，但是没必要；若按前、后序的交换方式，来处理中序（左中右），会出现左孩子被处理两次，而右孩子没有处理。
     * <p>
     * 当出现node的左孩子的左右孩子成功交换顺序，然后node的左孩子就会被换到右边，而原来的右孩子换到左边；
     * <p>
     * 接着处理新的右孩子（即旧的左孩子），那么node本来的左孩子就会被处理两次，而右孩子没有处理。
     *<p>
     * 若非要中序实现也可以，那处理左孩子——>中序（交换左右）——>处理右孩子，在处理右孩子时，实际要处理的是交换前的右孩子，也就是处理交换后的新的左孩子node.left
     */

    /**
     * 个解-BFS：队列，前序遍历；
     * 把每一个节点的左右孩子翻转一下。思路类似栈
     */
    public TreeNode invertTree4(TreeNode root) {
        if (root == null) return null;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int curLevelSize = queue.size();
            for (int i = 0; i < curLevelSize; i++) {
                TreeNode poll = queue.poll();
                // 交换当前节点的左右孩子
                TreeNode tmp = poll.left;
                poll.left = poll.right;
                poll.right = tmp;

                // 入队左右孩子（虽然此时左右孩子节点已经被交换，但是不影响最后结果）
                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);

                /*
                // 这段放到后面，就是后序遍历的顺序；这种方式入队时，左右孩子节点顺序没有被改变
                TreeNode tmp = poll.left;
                poll.left = poll.right;
                poll.right = tmp;
                */
            }
        }

        return root;
    }

    /**
     * 个解（用栈）-前序遍历
     * <p>
     * 分析：递归本质是栈实现的，所以先理解本题递归的思路，栈也是类似。
     */
    public TreeNode invertTree3(TreeNode root) {
        if (root == null) return null;

        Stack<TreeNode> st = new Stack<>();
        TreeNode pop, tmp;
        st.push(root);
        while (!st.isEmpty()) {
            // 交换栈顶元素左右
            pop = st.pop();
            tmp = pop.left;
            pop.left = pop.right;
            pop.right = tmp;

            // 左右子树分别入栈（非空入栈）
            if (pop.left != null) st.push(pop.left);
            if (pop.right != null) st.push(pop.right);
        }
        return root;
    }

    /**
     * 个解2-前序遍历；
     * 递归返回值为void
     */
    public TreeNode invertTree2(TreeNode root) {
        invert2(root);
        return root;
    }

    public void invert2(TreeNode node) {
        if (node == null) return;

        // 交换左右子树
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
        // 向下递归
        invert2(node.left);
        invert2(node.right);
    }

    /**
     * 个解1（参考官解）-前序遍历；
     * 递归返回值为TreeNode
     */
    public TreeNode invertTree(TreeNode root) {
        // 递归
        // 1.递归参数和返回值；
        // 入参：TreeNode node；返回值：TreeNode node
        // 2.终止条件
        // 节本层点为null
        // 3.单层递归逻辑
        // 交换左右 孩子节点，不仅仅是值

        // 递归终止条件
        // 应该是当前节点为空才终止，这样传入null也可以
//        if (root.left == null && root.right == null) return root;
        if (root == null) return root;

        // 单层递归逻辑：交换左右子节点(而不只是节点值)，然后分别处理左右子树
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 向下递归
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }

}
